package com.xiayuanxing.arithmetic.DataStructures.Tree;

import sun.awt.SunHints;

/**
 * @program: arithmetic
 * @description: 二叉排序树(BST )
 * @author: xia yuan xing
 * @create: 2021-10-13 10:48
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {

        int[] arr = {7,3,10,12,5,1,9,2};

        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Nade(arr[i]));
        }
        binarySortTree.infixOrder();

        System.out.println("删除节点后");
        binarySortTree.deleteNade(2);
        binarySortTree.infixOrder();

    }
}



class BinarySortTree{
    private Nade root;

    /**
     * 添加节点
     * @param nade
     */
    public void add(Nade nade){
        if (root != null){
            root.add(nade);
        }else {
            root = nade;
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if (root != null){
            root.infixOrder();
        }else {
            System.out.println("二叉排序树为空，不能遍历");
        }
     }


    /**
     * 查找要删除的节点
     * @param value
     * @return
     */
    public Nade search(int value){
        if (root == null){
            return null;
        }else {
            return  root.search(value);
        }
    }


    /**
     * 查找要删除节点的父节点
     * @param value
     * @return
     */
    public Nade searchParent(int value){
        if (root == null){
            return null;
        }else {
            return  root.searchParent(value);
        }
    }


    /**
     * 删除节点
     * @param value
     */
    public void deleteNade(int value){
        if (root == null){
            return;
        }else {
            //1.先去找需要删除的节点 targetNade
            Nade targetNade = search(value);
            //如果没有找到要删除的节点
            if (targetNade == null){
                return;
            }
            //如果当前二叉排序树只有一个节点
            if (root.left == null && root.right == null){
                root = null;
                return;
            }
            //去找到targetNade节点的父节点
            Nade parent = searchParent(value);
            //如果要删除的节点是叶子节点
            if(targetNade.left == null && targetNade.right == null){
                //判断targetNade是父节点的左子节点还是右子节点
                if (parent.left != null && parent.left.value == value){
                    //是左子节点
                    parent.left = null;
                }else if (parent.right != null && parent.right.value == value){
                    //是右子节点
                    parent.right = null;
                }
            }else if (targetNade.left != null && targetNade.right != null){
                //删除有两棵子树的节点
                int minValue = delRightTreeMin(targetNade.right);
                targetNade.value = minValue;
            }else {
                //删除有一棵子树的节点
                //如果要删除的节点有左子节点
                if (targetNade.left != null){
                    if (parent != null) {
                        //如果targetNade是parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNade.left;
                        } else {
                            parent.right = targetNade.left;
                        }
                    }else {
                        root = targetNade.left;
                    }
                }else {
                    //如果要删除的节点有右子节点
                    //如果targetNade是parent的左子节点
                    if (parent != null) {
                        if (parent.left.value == value) {
                            parent.left = targetNade.right;
                        } else {
                            //如果targetNade是parent的右子节点
                            parent.right = targetNade.right;
                        }
                    }else {
                        root = targetNade.right;
                    }
                }

            }

        }
    }


    /**
     * 1.返回一nade为根节点的二叉排序树的最小节点的值
     * 2.删除nade为根节点的二叉排序树的最小节点
     * @param nade 传入的节点（当做二叉排序树的根节点）
     * @return 返回的nade 为根节点的二叉排序树的最小节点的值
     */
     public int delRightTreeMin(Nade nade){
         Nade target = nade;
         //循环查找左子节点，就会找到最小的节点
         while (target.left != null){
             target = target.left;
         }
         //删除最小节点
         deleteNade(target.value);
         //返回最小节点的值
         return target.value;
     }

}


class Nade{

    int value;
    Nade left;
    Nade right;

    public Nade(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Nade{" +
                "value=" + value +
                '}';
    }

    /**
     * 添加节点
     * @param nade
     */
    public void add(Nade nade){
        if (nade == null){
            return;
        }
        //判断传入的节点的值，和当前子树的根节点的值的关系
        if (nade.value < this.value){
            //如果当前节点的左子节点为空
            if (this.left == null){
                this.left = nade;
            }else {
                //递归向左子树添加
                this.left.add(nade);
            }
        }else {
            //添加的节点的值大于当前节点的值
            if (this.right == null){
                this.right = nade;
            }else {
                //递归向右子树添加
                this.right.add(nade);
            }
        }



    }


    /**
     * 中序遍历
     */
    public void infixOrder(){
        if (this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null){
            this.right.infixOrder();
        }
    }


    /**
     * 查找要删除的节点
     * @param value 希望删除节点的值
     * @return 如果找到该值返回该节点，否则返回null
     */
    public Nade search(int value){
        //判断当前节点是否是该节点
        if (value == this.value){
            return this;
        }else if (value < this.value){
            //如果查找的值小于当前节点，向左子树递归查找
            if (this.left == null){
                return null;
            }
            return this.left.search(value);
        }else {
            //如果查找的值大于当前节点，向右子树递归查找
            if (this.right == null){
                return null;
            }
            return this.right.search(value);
        }
    }


    /**
     * 查找要删除的节点父节点
     * @param value 希望删除节点的值
     * @return 如果找到该值返回该节点父节点，否则返回null
     */
    public Nade searchParent(int value){
        //如果当前节点就是要删除的节点的父节点，就返回
        if ((this.left != null && this.left.value == value)||
                (this.right != null && this.right.value == value)
        ){
            return this;
        }else {
            //如果查找的值小于当前节点的值，并且当前节点的左子节点不为空
            if (value < this.value && this.left != null){
                //向左子树递归查找
                return this.left.searchParent(value);
            }else if (value >= this.value && this.right != null){
                //向右子树递归查找
                return this.right.searchParent(value);
            }else {
                return null;
            }
        }

    }


}